package com.njupt.backtracking;

/**
 * @Author: wujiaming
 * @CreateTime: 2025/2/12 15:24
 * @Description: 79. 单词搜索
 * @Version: 1.0
 */


public class Exist_79 {

    public static int DIR[][] = {{0,1},{1,0},{-1,0},{0,-1}};

    public  boolean isValid = false;

    /**
     * 法一：图的深度优先遍历 + 回溯
     * @param board
     * @param word
     * @return
     */
    public boolean exist(char[][] board, String word) {
        int m = board.length;
        int n = board[0].length;

        boolean[][] isVisited = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(board[i][j] == word.charAt(0)){

                    StringBuilder sb = new StringBuilder();
                    sb.append(board[i][j]);
                    isVisited[i][j] = true;
                    dfs(board,word,sb,i,j,isVisited);

                }
            }

        }

        return this.isValid;
    }


    private void dfs(char[][] board, String word, StringBuilder sb,int x,int y,boolean[][] isVisited) {

        if(sb.length() == word.length()){
            if(sb.toString().equals(word)){
                this.isValid = true;
            }
            return;
        }

        for (int i = 0; i < DIR.length; i++) {
            int nextX = x + DIR[i][0];
            int nextY = y + DIR[i][1];
            if(nextX < 0 || nextX >= board.length || nextY < 0 || nextY >= board[0].length) continue;
            if(!isVisited[nextX][nextY]){
                sb.append(board[nextX][nextY]);
                isVisited[nextX][nextY] = true;
                dfs(board,word,sb,nextX,nextY,isVisited);
                if(this.isValid){
                    return;
                }
                sb.deleteCharAt(sb.length()-1);
                isVisited[nextX][nextY] = false;
            }

        }
        isVisited[x][y] = false;

    }


    /**
     * 不适用stringbuilder记录深度搜索过程的结果，
     * 而是每搜索一个字符就和字符串的当前位置的字符比较，
     *  只要有一个字符不相等那么就直接返回false
     *  直到访问到字符串的末尾就返回false
     * @param board
     * @param word
     * @return
     */
    public boolean exist1(char[][] board, String word) {
        int m = board.length;
        int n = board[0].length;
        boolean[][] isVisited = new boolean[m][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                boolean flag = dfsCheck(board,word,isVisited,i,j,0);
                if(flag){
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfsCheck(char[][] board, String word, boolean[][] isVisited, int x,int y,int index) {
        if(board[x][y] != word.charAt(index)){
            return false;
        }

        if(index == word.length()-1){
            return true;
        }

        isVisited[x][y] = true;
        boolean result = false;
        for (int[] ints : DIR) {
            int nextX = x + ints[0];
            int nextY = y + ints[1];

            if(nextX < 0 || nextX >= board.length || nextY < 0 || nextY >= board[0].length) continue;

            if(!isVisited[nextX][nextY]){
                boolean flag = dfsCheck(board, word, isVisited, nextX, nextY, index + 1);
                if(flag){
                    result = true;
                    break;
                }
            }
        }
        isVisited[x][y] = false;
        return result;
    }


    public static void main(String[] args) {
        Exist_79 test = new Exist_79();
//        char[][] board = {{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}};
        char[][] board = {{'C','A','A'},{'A','A','A'},{'B','C','D'}};
        String word = "AAB";
        boolean exist = test.exist(board, word);
        System.out.println(exist);
    }
}
